package goleetcode

func orangesRotting(grid [][]int) int {
	directions := []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
	m, n := len(grid), len(grid[0])
	fresh := 0
	q := []pair{}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				fresh++
			} else if grid[i][j] == 2 {
				q = append(q, pair{i, j})
			}
		}
	}

	ans := -1
	for len(q) > 0 {
		ans++
		tmp := q
		q = []pair{}
		for _, p := range tmp {
			for _, d := range directions {
				i, j := p.x+d.x, p.y+d.y
				if 0 <= i && i < m && 0 <= j && j < n && grid[i][j] == 1 {
					fresh--
					grid[i][j] = 2
					q = append(q, pair{i, j})
				}
			}
		}
	}

	if fresh > 0 {
		return -1
	}

	return max(ans, 0)
}

type pair struct {
	x, y int
}
